package Arrays;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _488_FindAllNumbersDisappearedinanArray {
    //use list will over time,use hashset can be accepted
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> tempSet = new HashSet<Integer>();
        for(int i=0;i<nums.length;i++) {
            if (!tempSet.contains(nums[i])) {
                tempSet.add(nums[i]);
            }
        }
        List<Integer> resultLists = new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++) {
            if (!tempSet.contains(i + 1)) {
                resultLists.add(i+1);
            }
        }
        return resultLists;
    }

    //another solution
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        List<Integer> ret = new ArrayList<Integer>();

        for(int i = 0; i < nums.length; i++) {
            int val = Math.abs(nums[i]) - 1;
            if(nums[val] > 0) {
                nums[val] = -nums[val];
            }
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                ret.add(i+1);
            }
        }
        return ret;
    }

    //solution 2 by myself
    public List<Integer> findDisappearedNumbers2(int[] nums) {
        ArrayList<Integer> resultList =new ArrayList();
        boolean[] exists = new boolean[nums.length];
        for(int i=0;i<nums.length;i++) {
            exists[nums[i]-1] = true;
        }
        for(int i=0;i<nums.length;i++) {
            if (!exists[i]) {
                resultList.add(i+1);
            }
        }
        return resultList;
    }
}
